I'm not sure this "fixable" on Ubuntu with the standard build of openconnect, at least not by messing with system default priorities for gnutls. Correct me if I'm wrong but I've done some digging this morning and comparing the openconnect build on ubuntu 19.10 against the fedora build the main difference with regards to the priority strings is that the fedora build is specifically checking for a system or openconnect default policy:

@OPENCONNECT,SYSTEM:%COMPAT

Which I believe allows you to override via system level policies for the priority string, hence the update-crypto-policies noted in the link above. On Ubuntu 19.10, this is the policy string I see in libopenconnect.so.5.5.0:

NORMAL:-VERS-SSL3.0:%COMPAT

If it had a similar policy string, for example @SYSTEM or @OPENCONNECT, you could theoretically (I haven't tested) override OpenConnect's default using /etc/gnutls/config. I tested this priority string, which is what Fedora sets when enabling legacy crypto, and gnutls-cli does not complain when connecting to the AnyConnect host I have this issue with.

$ cat /etc/gnutls/config 
[priorities]
SYSTEM=NORMAL:+3DES-CBC:+ARCFOUR-128

$ gnutls-cli --priority @SYSTEM --list
Cipher suites for @SYSTEM
TLS_AES_256_GCM_SHA384                            	0x13, 0x02	TLS1.3
TLS_CHACHA20_POLY1305_SHA256                      	0x13, 0x03	TLS1.3
TLS_AES_128_GCM_SHA256                            	0x13, 0x01	TLS1.3
TLS_AES_128_CCM_SHA256                            	0x13, 0x04	TLS1.3
TLS_ECDHE_ECDSA_AES_256_GCM_SHA384                	0xc0, 0x2c	TLS1.2
TLS_ECDHE_ECDSA_CHACHA20_POLY1305                 	0xcc, 0xa9	TLS1.2
TLS_ECDHE_ECDSA_AES_256_CCM                       	0xc0, 0xad	TLS1.2
TLS_ECDHE_ECDSA_AES_256_CBC_SHA1                  	0xc0, 0x0a	TLS1.0
TLS_ECDHE_ECDSA_AES_128_GCM_SHA256                	0xc0, 0x2b	TLS1.2
TLS_ECDHE_ECDSA_AES_128_CCM                       	0xc0, 0xac	TLS1.2
TLS_ECDHE_ECDSA_AES_128_CBC_SHA1                  	0xc0, 0x09	TLS1.0
TLS_ECDHE_ECDSA_3DES_EDE_CBC_SHA1                 	0xc0, 0x08	TLS1.0
TLS_ECDHE_ECDSA_ARCFOUR_128_SHA1                  	0xc0, 0x07	TLS1.0
TLS_ECDHE_RSA_AES_256_GCM_SHA384                  	0xc0, 0x30	TLS1.2
TLS_ECDHE_RSA_CHACHA20_POLY1305                   	0xcc, 0xa8	TLS1.2
TLS_ECDHE_RSA_AES_256_CBC_SHA1                    	0xc0, 0x14	TLS1.0
TLS_ECDHE_RSA_AES_128_GCM_SHA256                  	0xc0, 0x2f	TLS1.2
TLS_ECDHE_RSA_AES_128_CBC_SHA1                    	0xc0, 0x13	TLS1.0
TLS_ECDHE_RSA_3DES_EDE_CBC_SHA1                   	0xc0, 0x12	TLS1.0
TLS_ECDHE_RSA_ARCFOUR_128_SHA1                    	0xc0, 0x11	TLS1.0
TLS_RSA_AES_256_GCM_SHA384                        	0x00, 0x9d	TLS1.2
TLS_RSA_AES_256_CCM                               	0xc0, 0x9d	TLS1.2
TLS_RSA_AES_256_CBC_SHA1                          	0x00, 0x35	TLS1.0
TLS_RSA_AES_128_GCM_SHA256                        	0x00, 0x9c	TLS1.2
TLS_RSA_AES_128_CCM                               	0xc0, 0x9c	TLS1.2
TLS_RSA_AES_128_CBC_SHA1                          	0x00, 0x2f	TLS1.0
TLS_RSA_3DES_EDE_CBC_SHA1                         	0x00, 0x0a	TLS1.0
TLS_RSA_ARCFOUR_128_SHA1                          	0x00, 0x05	TLS1.0
TLS_DHE_RSA_AES_256_GCM_SHA384                    	0x00, 0x9f	TLS1.2
TLS_DHE_RSA_CHACHA20_POLY1305                     	0xcc, 0xaa	TLS1.2
TLS_DHE_RSA_AES_256_CCM                           	0xc0, 0x9f	TLS1.2
TLS_DHE_RSA_AES_256_CBC_SHA1                      	0x00, 0x39	TLS1.0
TLS_DHE_RSA_AES_128_GCM_SHA256                    	0x00, 0x9e	TLS1.2
TLS_DHE_RSA_AES_128_CCM                           	0xc0, 0x9e	TLS1.2
TLS_DHE_RSA_AES_128_CBC_SHA1                      	0x00, 0x33	TLS1.0
TLS_DHE_RSA_3DES_EDE_CBC_SHA1                     	0x00, 0x16	TLS1.0

Protocols: VERS-TLS1.3, VERS-TLS1.2, VERS-TLS1.1, VERS-TLS1.0, VERS-DTLS1.2, VERS-DTLS1.0
Ciphers: AES-256-GCM, CHACHA20-POLY1305, AES-256-CCM, AES-256-CBC, AES-128-GCM, AES-128-CCM, AES-128-CBC, 3DES-CBC, ARCFOUR-128
MACs: SHA1, AEAD
Key Exchange Algorithms: ECDHE-ECDSA, ECDHE-RSA, RSA, DHE-RSA
Groups: GROUP-SECP256R1, GROUP-SECP384R1, GROUP-SECP521R1, GROUP-X25519, GROUP-FFDHE2048, GROUP-FFDHE3072, GROUP-FFDHE4096, GROUP-FFDHE6144, GROUP-FFDHE8192
PK-signatures: SIGN-RSA-SHA256, SIGN-RSA-PSS-SHA256, SIGN-RSA-PSS-RSAE-SHA256, SIGN-ECDSA-SHA256, SIGN-ECDSA-SECP256R1-SHA256, SIGN-EdDSA-Ed25519, SIGN-RSA-SHA384, SIGN-RSA-PSS-SHA384, SIGN-RSA-PSS-RSAE-SHA384, SIGN-ECDSA-SHA384, SIGN-ECDSA-SECP384R1-SHA384, SIGN-RSA-SHA512, SIGN-RSA-PSS-SHA512, SIGN-RSA-PSS-RSAE-SHA512, SIGN-ECDSA-SHA512, SIGN-ECDSA-SECP521R1-SHA512, SIGN-RSA-SHA1, SIGN-ECDSA-SHA1

$ gnutls-cli --priority @SYSTEM your-vpn-host.tld